#include<iostream>
using namespace std;
int if_connect(int map[][200],int visit[200],int n)
{
	int i = 0;
	int cur = 1;
	visit[cur] = 1;
	for (i=1; i <=n ; i++)
	{
		int j = 0;
		for (j=1; j <= n; j++)
		{
			if (map[cur][j] == 1 && visit[j] == 0)
			{
				visit[j] = 1;
				cur = j;
				break;
			}
		}
	}
	int j = 0;
	for (j; j < n; j++)
	{
		if (visit[j] == 0)
			return 0;
	}
	return 1;
}
int main()
{
	int flag = 1;
	while (flag)
	{
		int n, k;
		cin >> n ;
		if (n == 0)
			break;
		cin >> k;
		int map[200][200] = { 0 };
		int visit[200] = { 0 };
		visit[0] = 1;
		int i = 0;
		for (i; i < k; i++)
		{
			int m, j;
			cin >> m >> j;
			map[m][j] = 1;
			map[j][m] = 1;
		}
		int flag2 = if_connect(map, visit, n);
		if (flag2)
		{
			int flag3 = 0;
			for (i = 0; i <= n; i++)
			{
				int j = 0;
				for (j; j <= n; j++)
				{
					map[i][n+1] += map[i][j];
				}
				if (map[i][n+1] % 2 == 1)
				{
					flag3 = 1;
					break;
				}
			}
			if (flag3)
				cout << "0" << endl;
			else
				cout << "1" << endl;
		}
		else
		{
			cout << "0" << endl;
		}
	}
}